W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W środku nocy Bitocy włączył latarnię przy wejściu do budynku, w którym mieszka Bajtazar. Światło latarni nie daje spać Bajtazarowi. Co prawda, latarnia nie świeci bezpośrednio w okno Bajtazara, ale jej światło odbija się od innych okien i wpada w okno Bajtazara. Bajtazar nie może zasnąć i denerwuje się. Żeby czymś zająć umysł, zamiast się denerwować, Bajtazar wygląda przez okno i zastanawia się, w które jeszcze okna świeci latarnia. Problem ten wciągnął go na tyle, że zapomniał o śnie i zadzwonił do Ciebie, prosząc o pomoc. Znasz Bajtazara nie od dziś i wiesz, że póki nie napiszesz dla niego programu rozwiązującego ten problem, sam(a) też nie pójdziesz spać.
Bajtazar mieszka w budynku , w którym jest okien. Latarnia znajduje się na samym dole budynku, na ścianie. Naprzeciwko budynku stoi budynek , oddalony o 10 metrów. Jego ściana jest równoległa do ściany budynku Bajtazara. Budynek ma okien.
Światło latarni rozchodzi się po liniach prostych, chyba że trafi w okno - wtedy mówimy, że latarnia świeci w to okno, a światło latarni odbija się od niego (zgodnie z zasadą "kąt padania równa się kątowi odbicia").
Na ścianach budynków mamy określone układy współrzędnych - oś jest pozioma, oś jest pionowa, osie na obu ścianach mają zgodne zwroty, a punkty na obu ścianach leżą dokładnie naprzeciwko siebie. Okna to prostokąty położone na ścianach o bokach równoległych do osi układu współrzędnych. Światło nie odbija się od brzegów okien. Ponadto wiadomo, że okna w obrębie jednego budynku mają parami rozłączne wnętrza. Latarnia znajduje się na ścianie budynku w punkcie i nie znajduje się we wnętrzu ani na brzegu żadnego z okien.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (), oddzielone pojedynczym odstępem, oznaczające liczbę okien w pierwszym i w drugim budynku. W kolejnych wierszach opisane są okna w budynku Bajtazara (budynek ), po jednym w wierszu.
W -szym wierszu (dla ) znajdują się cztery liczby całkowite , , , (, ), pooddzielane pojedynczymi odstępami. Taka czwórka oznacza, że -te okno znajdujące się w budynku stanowi prostokąt na ścianie budynku, którego lewy dolny i prawy górny róg mają współrzędne i , wyrażone w metrach.
Następnie w kolejnych wierszach, w tym samym formacie, opisane są okna budynku .
Twój program powinien wypisać w pierwszym wierszu standardowego wyjścia liczbę okien budynku , w które świeci latarnia. Możesz założyć, że dla każdych danych wejściowych będzie istniało co najmniej jedno takie okno.
W drugim wierszu należy wypisać numery tych okien, podane w kolejności rosnącej, pooddzielane pojedynczymi odstępami (okna numerujemy od ).
Dla danych wejściowych:
3 3 -1 2 1 4 -1 5 1 7 -3 8 -2 20 -1 1 1 2 -1 4 1 5 -1 7 1 10
poprawną odpowiedzią jest:
2 1 2
Wyjaśnienie do przykładu: Do pierwszego okna budynku światło dolatuje, odbiwszy się od pierwszego okna w budynku (np. odbija się w punkcie budynku i trafia w punkt budynku ). Żeby trafić w drugie okno budynku , światło latarni musi odbić się trzy razy - ten sam promień trafia w punkt w drugim oknie budynku , a potem w w drugim oknie budynku . Światło nie trafia w trzecie okno budynku , tylko obok niego. Należy dodać, że światło latarni oświetla cały budynek , na rysunku natomiast zaznaczono tylko te promienie świetlne, które po odbiciu oświetlają okna budynku .
Autor zadania: Jakub Onufry Wojtaszczyk.